#include "main.h"

void countingSort(int* array, int len, int max, int beg, GetKey getKey)
{
	int* count = new int[max+1];
	int* resArray = new int[len];

	for (int i = 0; i <= max; ++i)
	{
		count[i] = 0;
	}

	for (int i = beg; i < beg + len; ++i)
	{
		count[ getKey(array[i]) ]++;
	}

	for (int i = 1; i <= max; ++i)
	{
		count[i] += count[i-1];
	}

	// i decreases from len-1 to 0 so that the order of equal elements is preserved
	for (int i = beg + len - 1; i >= beg; --i)
	{
		resArray[ count[ getKey(array[i]) ]-1 ] = array[i];
		count[ getKey(array[i]) ]--;
	}

	for (int i = 0; i < len; ++i)
	{
		array[i + beg] = resArray[i];
	}

	delete [] count;
	delete [] resArray;
}
